package leetcode_400;

import java.util.Stack;

/**
 *@author 周杨
 *CreateMaximumNumber_321_ 给定两个数组和长度k 返回一个数组 这个数组是长度为k的最大数 其中由两数组序列组成
 *describe:用贪心算法 每次保证自己找的数在范围内 且为最大  有点难 AC 15%
 *2018年7月3日 下午3:24:46
 */
public class CreateMaximumNumber_321_ {

	public static void main(String[] args) {
		CreateMaximumNumber_321_ test=new CreateMaximumNumber_321_();
		//test.print(test.getMax(new int[] {9, 1, 2, 5, 8, 3}, 2));
		test.print(test.maxNumber(new int[] {6,7}, new int[] {6,7,4}, 5));

	}
	
	/**
	 * describe:笨办法 每次查看该坐标给出的最大数
	 * 2018年7月3日 下午3:24:05
	 */
	public int[] maxNumber1(int[] nums1, int[] nums2, int k) {
        int[] res = new int[k];
        for(int i = 0; i <= k; i ++) {
            int j = k - i;
            if(i > nums1.length || j > nums2.length) continue;
            int[] digits1 = find(nums1, i);
            int[] digits2 = find(nums2, j);
            int[] digits = merge(digits1, digits2);
            res = compare(digits, res) > 0? digits: res;
        }
        return res;
    }
    
    public int[] find(int[] nums, int count) {
        int n = nums.length, remain = count;
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0; i < n; i ++) {
            while(!stack.isEmpty() && nums[i] > stack.peek() && n - i - 1 >= remain) {
                stack.pop();
                remain ++;
            }
            if(remain > 0) {
                stack.push(nums[i]);
                remain --;
            }
        }
        int[] num = new int[count];
        int i = 0;
        for(Integer s: stack) {
            num[i ++] = s.intValue();
        }
        return num;
    }
    
    public int[] merge(int[] digits1, int[] digits2) {
        int i = 0, j = 0, p = 0, len1 = digits1.length, len2 = digits2.length;
        int[] res = new int[len1 + len2];
        while(i < len1 && j < len2) {
            if(digits1[i] > digits2[j]) {
                res[p ++] = digits1[i ++];
            } else if(digits1[i] < digits2[j]) {
                res[p ++] = digits2[j ++];
            } else {
                int istart = i, jstart = j;
                while(i < len1 && j < len2 && digits1[i] == digits2[j]) {
                    i ++;
                    j ++;
                }
                if(( i < len1 & j < len2 && digits1[i] > digits2[j]) 
                  || (j == len2)) {
                    res[p ++] = digits1[istart ++];
                } else {
                    res[p ++] = digits2[jstart ++];
                }
                i = istart;
                j = jstart;
            }
        }
        while(i < len1) {
            res[p ++] = digits1[i ++];
        }
        while(j < len2) {
            res[p ++] = digits2[j ++];
        }
        return res;
    }
    
    public int compare(int[] n1, int[] n2) {
        for(int i = 0; i < n1.length; i ++) {
            if(n1[i] < n2[i]) return -1;
            else if(n1[i] > n2[i]) return 1;
        }
        return 0;
    }
	
	
	public void print(int []nums) {
		for(int i:nums)
			System.out.print(i+" ");
	}
	/**
	 * describe:给定一个数组 返回其k位的最大数 要求元素顺序不变
	 * 2018年7月3日 上午9:49:46
	 */
	public int[] getMax(int []nums,int k) {
		int res[]=new int[k];
		int index=0;
		int i=0;//安排第index位
		while(index<k) {
			int max=-1,level=-1;
			while(i-index<=nums.length-k) {//在此区间找最大值
				if(max<nums[i]) {
					level=i;
					max=nums[i];
				}
				++i;
			}
			res[index]=max;
			i=level+1;
			++index;
		}
		return res;
	}
	
	
	/**
	 * describe:我自己的贪心算法  但是在判断最高位相等后的逻辑错误
	 * 2018年7月3日 下午2:47:55
	 */
	public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int res[]=new int[k];
        int index=0,index1=0,index2=0;
        while(index<k) {
        	int max1=-1,max2=-1,level1=-1,level2=-1,run1=index1,run2=index2;//及时回退
        	while(run1<nums1.length&&nums1.length-run1+nums2.length-index2>=k-index) {//去找max
        		if(nums1[run1]>max1) {
        			level1=run1;
        			max1=nums1[run1];
        		}
        		++run1;
        	}
        	while(run2<nums2.length&&nums1.length-index1+nums2.length-run2>=k-index) {//去找max
        		if(nums2[run2]>max2) {
        			level2=run2;
        			max2=nums2[run2];
        		}
        		++run2;
        	}
        	if(max1>max2) {
        		res[index]=max1;
        		index1=level1+1;//改变Index1
        	}
        	else if(max1<max2) {
        		res[index]=max2;
        		index2=level2+1;
        	}
        	else {
        		if(help(nums1,level1+1,nums2,level2+1,k-index-2)) {
        			res[index]=max1;
            		index1=level1+1;
        		}
        		else {
        			res[index]=max2;
            		index2=level2+1;
        		}
        	}
        	++index;
        	
        }
        
        return res;
    }
	
	/**
	 * describe:该归并算法 通过了大部分用例 但是[3,9] [8,9]  3 没有过
	 * 2018年7月3日 下午3:19:11
	 */
	private boolean help(int[] nums1,int index1,int[] nums2,int index2,int left) {
		if(index1==nums1.length)
			return false;
		if(index2==nums2.length)
			return true;
		int run1=index1,run2=index2,max1=-1,max2=-1,level1=-1,level2=-1;
		while(run1<nums1.length&&nums1.length-run1+nums2.length-index2>=left) {
			if(max1<nums1[run1]) {
				max1=nums1[run1];
				level1=run1;
			}
			++run1;
		}
		while(run2<nums2.length&&nums1.length-index1+nums2.length-run2>=left) {
			if(max2<nums2[run2]) {
				max2=nums2[run2];
				level2=run2;
			}
			++run2;
		}
		if(max1>max2)
			return true;
		else if(max1<max2)
			return false;
		else
			return help(nums1,level1+1,nums2,level2+1,left-2);
	}
	
	
}
